package Algorithm.DynamicPlanning;

// 最长递增子序列
public class Code13_LIS {

    public static int[] list1(int[] arr){
        if (arr == null || arr.length == 0){
            return null;
        }
        int[] dp = getdp1(arr);
        return generateLIS(arr, dp);
    }

    public static int[] getdp1(int[] arr){
        int[] dp = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++){
                if (arr[j] < arr[i]){
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        return dp;
    }

    public static int[] generateLIS(int[] arr, int[] dp){
        int max = Integer.MIN_VALUE;
        // 找到dp中最大值
        for (int i = 0; i < dp.length; i++) {
            max = Math.max(max, dp[i]);
        }
        int val = 1;
        int[] res = new int[max];
        for (int i = 0; i < arr.length; i++) {
            if (dp[i] == max){
                res[max - 1] = arr[i];
                break;
            }
            if (dp[i] == val){
                res[val - 1] = arr[i];
                val++;
            }
        }
        return res;
    }

    public static int[] list2(int[] arr){
        if (arr == null || arr.length == 0){
            return null;
        }
        int[] dp = new int[arr.length];
        int[] ends = new int[arr.length];
        ends[0] = arr[0];
        dp[0] = 1;
        int r = 0; // 记录ends当前最右数下标
        boolean flag = false;
        for (int i = 1; i < arr.length; i++) {
            // 填充ends，二分找比arr[i]大的数，有则更新ends对应位置；没有扩充ends
            // dp：ends数组中从左数包括自己一共多少数
            /**
            for (int j = 0; j <= r; j++){
                if (ends[j] > arr[i]) {
                    ends[j] = arr[i];
                    dp[i] = j + 1;
                    flag = true;
                    break;
                }
            }
            if (!flag){
                ends[r++] = arr[i];
                dp[i] = r + 1;
            } else {
                flag = false;
            }
             **/
            int left = 0;
            int right = r;
            while (left <= right){ // 找到ends中大于arr[i]的数最靠左的
                int mid = left + ((right - left) >> 1);
                if (ends[mid] > arr[i]){ // 再向左走
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            
        }
        return generateLIS(arr, dp);
    }

    public static void main(String[] args) {
        int[] arr = { 2, 1, 5, 3, 6, 4, 8, 9, 7 };
        int[] res = list1(arr);
        for (int i = 0; i < res.length; i++) {
            System.out.print(res[i] + " ");
        }
        System.out.println();
        int[] res2 = list2(arr);
        for (int i = 0; i < res2.length; i++) {
            System.out.print(res2[i] + " ");
        }
    }
}
